package 数字在排序数组中出现的次数;

//题目描述
//统计一个数字在排序数组中出现的次数。
public class Solution
{
    //暴力遍历方法，没有用到数组有序的条件
    public int GetNumberOfK1(int[] array, int k)
    {
        //判断输入
        if (array == null || array.length == 0) return 0;
        int count = 0;
        for (int i = 0; i < array.length; i++)
        {
            if (array[i] == k)
                count++;

        }
        return count;
    }

    //二分查找法，。两次
    public int GetFirstK(int[] array, int left, int right, int k)
    {
        if (left > right)
            return -1;
        int midindex = (left + right) / 2;
        int middata = array[midindex];
        if (middata == k)
        {
            //特殊情况，直接找到第一个k
            if ((midindex > left && array[midindex - 1] < k) || midindex == left)
                return midindex;
            else right = midindex - 1;//往前半段找，所以改right
        } else if (middata < k)
        {
            //k在后半段
            left = midindex + 1;
        } else
            right = midindex - 1;
        return GetFirstK(array, left, right, k);

    }

    public int GetLastK(int[] array, int left, int right, int k)
    {
        if (left > right)
            return -1;
        int midindex = (left + right) / 2;
        int middata = array[midindex];
        if (middata == k)
        {
            //特殊情况，直接找到最后一个k
            if (midindex == right || (midindex < right && array[midindex + 1] > k))
                return midindex;
            else
                left = midindex + 1;
        } else if (middata < k)
        {
            //k在后半段
            left = midindex + 1;
        } else
            right = midindex - 1;
        return GetLastK(array, left, right, k);
    }

    public int GetNumberOfK(int[] array, int k)
    {

        //判断输入
        int number = 0;
        if (array != null && array.length > 0)
        {
            int firstk = GetFirstK(array, 0, array.length - 1, k);
            int lastk = GetLastK(array, 0, array.length - 1, k);
            if (firstk > -1 && lastk > -1)
                number = lastk - firstk + 1;
        }
        return number;
    }

    public static void main(String[] args)
    {
        Solution solution = new Solution();
        System.out.println(solution.GetNumberOfK(new int[]{1, 2, 3, 3, 3, 3, 4, 5}, 3));

    }

}
